using System;
using System.Collections.Generic;
using System.Text;

namespace Ndo
{
    public abstract class TreeNodeBase<TFinal> : Object<TFinal>
        where TFinal: TreeNodeBase<TFinal>
    {
        protected TreeNodeBase()
        {
        }

        public abstract TFinal Parent { get;}
        public TFinal Root
        {
            get
            {
                TFinal t = this.Parent;
                if(t == null)
                    return null;
                while (t.Parent != null)
                    t = t.Parent;
                return t;
            }
        }

        public IEnumerable<TFinal> Path
        {
            get
            {
                TFinal t = this.Self;
                do
                {
                    yield return t;
                    t = t.Parent;
                } while (t != null);
            }
        }
        public IEnumerable<TFinal> AllNodes
        {
            get
            {
                return this.DepthFirstTraersal;
            }
        }
        public IEnumerable<TFinal> DepthFirstTraersal
        {
            get
            {
                yield return this.Self;
                foreach (TFinal node in this.Nodes)
                {
                    foreach (TFinal t in node.DepthFirstTraersal)
                    {
                        yield return t;
                    }
                }
            }
        }
        public IEnumerable<TFinal> BreadthFirstTraversal
        {
            get
            {
                Queue<TFinal> q = new Queue<TFinal>();
                q.Enqueue(this.Self);
                do
                {
                    TFinal t = q.Dequeue();
                    yield return t;
                    foreach (TFinal node in t.Nodes)
                    {
                        q.Enqueue(node);
                    }
                } while (q.Count > 0);
            }
        }
        public abstract ICollection<TFinal> Nodes{ get;}
        public abstract void Put(TFinal node);
        public abstract bool Add(TFinal node);
        public abstract bool Remove(TFinal node);
        public abstract void Delete();
        public abstract void Clear();
        public abstract bool Contains(TFinal node);
        public abstract int Count{ get;}
    }

    public class TreeNode<TKey, TFinal> : TreeNodeBase<TFinal>
         where TFinal : TreeNode<TKey, TFinal>
    {
        public TreeNode(TKey key)
        {
            this.key = key;
        }

        private TFinal parent;
        public override TFinal Parent
        {
            get { return this.parent; }
        }
        private readonly TKey key;
        public TKey Key
        {
            get { return key; }
        }
        private Dictionary<TKey, TFinal> dict = new Dictionary<TKey, TFinal>();
        public TFinal this[TKey key]
        {
            get { return this.dict[key]; }
        }

        public ICollection<TKey> Keys
        {
            get { return this.dict.Keys; }
        }
        public override ICollection<TFinal> Nodes
        {
            get { return this.dict.Values; }
        }

        public override void Delete()
        {
            if (this.parent != null)
            {
                this.parent.dict.Remove(this.key);
                this.parent = null;
            }
        }
        public override void Put(TFinal node)
        {
            TFinal t;
            if(this.dict.TryGetValue(node.key, out t))
            {
                t.parent = null;
            }
            if (node.parent != null)
            {
                node.parent.dict.Remove(node.key);
            }
            node.parent = this.Self;
            this.dict[node.key] = node;
        }
        public override bool Add(TFinal node)
        {
            if (this.dict.ContainsKey(node.key))
            {
                return false;
            }
            if (node.parent != null)
            {
                node.parent.dict.Remove(node.key);
            }
            node.parent = this.Self;
            this.dict.Add(node.key, node);
            return true;
        }

        public bool ContainsKey(TKey key)
        {
            return this.dict.ContainsKey(key);
        }

        public bool RemoveKey(TKey key)
        {
            TFinal t;
            if (this.dict.TryGetValue(key, out t))
            {
                t.parent = null;
                this.dict.Remove(key);
                return true;
            }
            return false;
        }

        public override bool Remove(TFinal node)
        {
            if(node.parent != this)
            {
                return false;
            }
            TFinal t;
            if (this.dict.TryGetValue(node.key, out t) && t == node)
            {
                t.parent = null;
                this.dict.Remove(node.key);
                return true;
            }
            return false;
        }

        public bool TryGetValue(TKey key, out TFinal value)
        {
            return this.dict.TryGetValue(key, out value);
        }

        public override void Clear()
        {
            foreach (TFinal t in dict.Values)
            {
                t.parent = null;
            }
            this.dict.Clear();
        }

        public override bool Contains(TFinal node)
        {
            if (node.parent != this)
            {
                return false;
            }
            TFinal t;
            if (this.dict.TryGetValue(node.key, out t))
            {
                return t == node;
            }
            return false;
        }

        public override int Count
        {
            get { return this.dict.Count; }
        }
    }
    public class TreeNode<TFinal> : TreeNodeBase<TFinal>
         where TFinal : TreeNode<TFinal>
    {
        public TreeNode()
        {}

        private TFinal parent;
        public override TFinal Parent
        {
            get { return this.parent; }
        }
        private Dictionary<TFinal, TFinal> dict = new Dictionary<TFinal, TFinal>();
        public override ICollection<TFinal> Nodes
        {
            get { return this.dict.Values; }
        }

        public override void Delete()
        {
            if (this.parent != null)
            {
                this.parent.dict.Remove(this.Self);
                this.parent = null;
            }
        }

        public override void Put(TFinal node)
        {
            TFinal t;
            if (this.dict.TryGetValue(node, out t))
            {
                t.parent = null;
            }
            if (node.parent != null)
            {
                node.parent.dict.Remove(node);
            }
            node.parent = this.Self;
            this.dict[node] = node;
        }
        public override bool Add(TFinal node)
        {
            if (this.dict.ContainsKey(node))
            {
                return false;
            }
            if (node.parent != null)
            {
                node.parent.dict.Remove(node);
            }
            node.parent = this.Self;
            this.dict.Add(node, node);
            return true;
        }

        public override bool Remove(TFinal node)
        {
            if(node.parent != this)
            {
                return false;
            }
            bool done = this.dict.Remove(node);
            if (done)
            {
                node.parent = null;
            }
            return done;
        }

        public override void Clear()
        {
            foreach (TFinal t in dict.Keys)
            {
                t.parent = null;
            }
            this.dict.Clear();
        }

        public override bool Contains(TFinal node)
        {
            if (node.parent != this)
            {
                return false;
            }
            return this.dict.ContainsKey(node);
        }

        public override int Count
        {
            get { return this.dict.Count; }
        }
    }
}
